package 链表和树.二叉树;
//Java：二叉树的最近公共祖先
public class LowestCommonAncestorOfABinaryTree{
    public static void main(String[] args) {
        Solution solution = new LowestCommonAncestorOfABinaryTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

//  public class TreeNode {
//      int val;
//      TreeNode left;
//      TreeNode right;
//      TreeNode(int x) { val = x; }
//  }

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //边界条件当前节点是空/p/q返回当前节点因为这是根节点
        if(root == null || root == p || root == q){
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p,q);
        TreeNode right = lowestCommonAncestor(root.right, p,q);
        //递归完p和q分布在左右节点那么root就是
        if(left != null && right != null){
            return root;
        }
        //上面判断完左右都在的情况下面就是单情况和左右都没有找到了
        //如果只有左子树找到返回左子树的返回值(两个节点都在左子树)
        //如果只有右子树找到返回右子树的返回值
        //如果都没有就返回null此时right = null = left可合并右为null的情况
        return left != null ? left : right;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}